<?php
class AStar{
    // A-star
    private $_open;     //OPEN表保存所有已生成而未考察的节点
    private $_closed;   //CLOSED表中记录已访问过的节点
    private $_start;
    private $_end;
    private $_grids;
    private $_w;
    private $_h;

    private $star = '*';    //地面
    private $sky = 0;       //墙

    private $_runMode;

    // Construct
    public function AStar(){
        $this->_w = null;
        $this->_h = null;
        $this->_grids = null;
        $this->_runMode = 1;
    }

    public function set($width, $height, $grids) {
        $this->_w = $width;
        $this->_h = $height;
        $this->_grids = $grids;
        return $this;
    }

    // 迷宫中寻路
    public function search($start = false, $end = false) {
        return $this->_search($start, $end);
    }

    /**
    |---------------------------------------------------------------
    | 自动寻路 - A-star 算法
    |---------------------------------------------------------------
    */
    private function _search($start = false, $end = false) {
        if ( $start !== false ) $this->_start = $start;
        if ( $end !== false ) $this->_end = $end;
        $tp = array();
        $_sh = $this->_getH($start);

        $point['i'] = $start;
        $point['f'] = $_sh;
        $point['g'] = 0;
        $point['h'] = $_sh;
        $point['p'] = null;
        $this->_open[] = $point;
        $this->_closed[$start] = $point;

        while ( 0 < count($this->_open) ) {
            $minf = false;
            foreach( $this->_open as $key => $maxNode ) {
                if ( $minf === false || $minf > $maxNode['f'] ) {
                    $minIndex = $key;
                }
            }
            $nowNode = $this->_open[$minIndex];
            unset($this->_open[$minIndex]);
            if ( $nowNode['i'] == $this->_end ) {
                
                while( $nowNode['p'] !== null ) {
                    array_unshift($tp, $nowNode['p']);
                    $nowNode = $this->_closed[$nowNode['p']];
                }
                array_push($tp, $this->_end);
                break;
            }
            $this->_setPoint($nowNode['i']);
        }

        $this->_closed = array();
        $this->_open = array();

        return $tp;
    }

    private function _setPoint($me) {
        // if($this->_runMode){
        //     echo 'DEBUG: '.__FUNCTION__.'('.$me.')'.PHP_EOL;
        // }
        if($me<0) return false;
        if(!isset($this->_grids[$me])) return false;

        $point = $this->_grids[$me];
        // 所有可选方向入队列
        if ( $point==$this->sky && 1 ) {
            $next = $me - $this->_w;        //上
            $this->_checkPoint($me, $next);
        }
        if ( $point==$this->sky && 2 ) {
            $next = $me + 1;                //右
            $this->_checkPoint($me, $next);
        }
        if ( $point==$this->sky && 4 ) {
            $next = $me + $this->_w;        //下
            $this->_checkPoint($me, $next);
        }
        if ( $point==$this->sky && 8 ) {
            $next = $me - 1;                //左边
            $this->_checkPoint($me, $next);
        }
    }

  //   private function _funcDebug($funcName) {
  //       switch ($funcName) {
  //           case '_funcDebug':
  //               return false;
  //               break;
            
  //           default:
  //               # code...
  //               break;
  //       }
		// return false;
  //   }

    private function _checkPoint($pNode, $next) {
        // if($this->_runMode){
        //     echo 'DEBUG: '.__FUNCTION__.'('.$pNode.','.$next.')'.PHP_EOL;
        // }

        if(!isset($this->_grids[$next])) {
            return false;
        }else if($this->_grids[$next]!=$this->sky){
            return false;
        }

        $dp=$this->_getDistanceByNode($pNode,$this->_end);
        $dn=$this->_getDistanceByNode($next,$this->_end);
				
        if($dp>$dn){
            // if($this->_runMode){
            //     echo 'DEBUG: '.__FUNCTION__.'() add new point '.$next.PHP_EOL;
            // }
            $point['p'] = $pNode;
            $point['h'] = $this->_getH($next);
            $point['g'] = $this->_getG($next);
            $point['f'] = $point['h'] + $point['g'];
            $point['i'] = $next;
            $this->_open[] = $point;
            $this->_closed[$next] = $point;
        }
        return false;
        /**
		if ( isset($this->_closed[$next])) {
//如果m 在 _closed 表中，则跳过该节点，返回
           return false;

        } else if(isset($this->_open[$next])) {
/*
如果m 已在 _open 表中，则比较刚计算的 f 新值和该节点m在表中的 f 旧值。
如果 f 新值较小，表示找到一条更好的路径，则以此新f 值取代表中该节点的 f 
旧值，将节点m父指针指向当前的n结点，而不是指向它的历史父节点
* /
        	$_g = $this->_getG($next);
            if($this->_runMode){
                echo 'DEBUG: '.__FUNCTION__.'() _g='.$_g.PHP_EOL;
            }

            if ( $_g < $this->_open[$next]['g'] ) {
                $this->_open[$next]['g'] = $_g;
                $this->_open[$next]['f'] = $this->_open[$next]['g'] + $this->_open[$next]['h'];
                $this->_open[$next]['p'] = $pNode;
            }

        }else{
/*
如果m不在 _open 表和 _closed 表中，把它添入 _open 表。
给m加一指向其父节点n的指针，以便找到目标节点时记住解答路径；
* /
			if($this->_runMode){
	            echo 'DEBUG: '.__FUNCTION__.'() add new point '.$next.PHP_EOL;
	        }

	        $point['p'] = $pNode;
	        $point['h'] = $this->_getH($next);
	        $point['g'] = $this->_getG($next);
	        $point['f'] = $point['h'] + $point['g'];
	        $point['i'] = $next;
	        $this->_open[] = $point;
	        // $this->_closed[$next] = $point;

        }

*/
    }

    private function _getG($point) {
    	//g(n) 是在状态空间中从初始节点到n节点的实际代价
        // return abs($this->_start - $point);
        return $this->_getDistanceByNode($this->_start,$point);
    }

    private function _getH($point) {
    	//h(n) 是从n到目标节点最佳路径的估计代价
        // return abs($this->_end - $point);
        return $this->_getDistanceByNode($this->_end,$point);
    }


    private function _getDistanceByNode($pos1,$pos2){
		$a = $this->_getNodeX($pos1)-$this->_getNodeX($pos2);
		$b = $this->_getNodeY($pos1)-$this->_getNodeY($pos2);
        return $a*$a + $b*$b;
    }

    private function _getNodeX($pos) {
        return fmod($pos,$this->_w);
        // $y = intval($pos/$this->_w);

    }

    private function _getNodeY($pos) {
        // $x = fmod($pos,$this->_w);
        return intval($pos/$this->_w);
    }

}